package LBLD新算法;

import org.junit.Test;

import java.util.Stack;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
public class 下一个更大元素_环形查找_503 {
    public int[] nextGreaterElements(int[] p) {
        int n=p.length;
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        //太巧：扩2倍，i%n配合之前旧笨只找右即可
        for (int i=2*n-1;i>=0 ;i--) {
            //用模板的话
            //小的滚
            while(!s.isEmpty()&&s.peek()<=p[i%n]){
                s.pop();
            }
            if(s.isEmpty()){
                res[i%n]=-1;
                s.push(p[i%n]);
            }
            else if(s.peek()>p[i%n]){
                res[i%n]=s.peek();
                s.push(p[i%n]);
            }
        }
        return res;
    }
}
